class Solution:
    def longestValidParentheses(self, s: 'str') -> 'int':
        dp = [0 for _ in range(len(s))]
        res = 0
        for i in range(1, len(s)):
            if s[i] == '(':
                continue
            prev = i - dp[i - 1] - 1
            if prev >= 0 and s[prev] == '(':
                dp[i] = 2 + dp[i - 1]
                if prev - 1 >= 0:
                    dp[i] += dp[prev - 1]
                res = max(res, dp[i])
        return res
